package 剑指offer;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 
 * @author 兰伟朋
 *@time 2020年12月10日上午11:25:28
 *@see
 *在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1
 * 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，
 * 也不知道每个数字重复了几次。
 * 请找出数组中任意一个重复的数字。
 */
public class _03数组中重复的数字 {
	/**
	 * 
	 *@time 2020年12月10日上午11:34:27
	 * 
	 *@param nums
	 *@return int
	 *使用临时数组
	 *这道题有个很明显的特点，就是数字的大小在0~n-1之间，
	 *所以使用上面两种方式肯定不是最好的选择。这里我们可以申请一个临时数组temp，
	 *因为nums元素中的每个元素的大小都在0~n-1之间，所以我们可以把nums中元素的值和临时数组temp建立映射关系，
	 *就是nums中元素的值是几，我们就把temp中对应的位置值加1，当temp某个位置的值大于1的时候，
	 *就表示出现了重复，我们直接返回即可
	 *@see
	 */
    public int findRepeatNumber1(int[] nums) {
    	int length=nums.length;
    	int temp[]=new int[length];
    	
    	for(int i=0;i<length;i++) {
    		temp[nums[i]]++;
    		if(temp[nums[i]]>1)
    			return nums[i];
    	}
		return -1;
    }
    /**
     * 
     *@time 2020年12月10日下午12:41:29
     * 
     *@param nums
     *@return int
     * 通过set集合的不重复属性
     * 
     * 
     * 
     * boolean	add​(E e)	
     * 如果指定的元素尚不存在，则将其添加到此集合中。
	 *	void	clear()	
	 *从该集中删除所有元素。
		Object	clone()	
		返回此 HashSet实例的浅表副本：未克隆元素本身。
		boolean	contains​(Object o)	
		如果此set包含指定的元素，则返回 true 。
		boolean	isEmpty()	
		如果此集合不包含任何元素，则返回 true 。
		Iterator<E>	iterator()	
		返回此set中元素的迭代器。
		boolean	remove​(Object o)	
		如果存在，则从该集合中移除指定的元素。
		int	size()	
		返回此集合中的元素数（基数）。
     *@see 使用集合set
     */
    public int findRepeatNumber2(int[] nums) {
    	Set<Integer> set=new HashSet<Integer>();
    	for (Integer s : nums) {			
    		if(!set.add(s)) 
    			return s;
		}
    	return -1;
    }
    /**
     * 先排序在查找
     */
    public int findRepeatNumber3(int[] nums) {
    	Arrays.sort(nums);
    	for(int i=1;i<nums.length;i++) {
    		if(nums[i-1]==nums[i]) 
    			return nums[i];   		
    	}
    	return -1;
    }
}
